struct TrieNode {
    TrieNode* children[26];
    string word = "";
    TrieNode() {
        for (int i = 0; i < 26; i++) {
            children[i] = nullptr;
        }
    }
};

class Solution {
private:
    vector<vector<char>> board;
    int m, n;
    vector<vector<bool>> visited;
    vector<vector<int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    vector<string> res;
public:
    vector<string> findWords(vector<vector<char>>& board, vector<string>& words) {
        this->board = board;
        this->m = (int)board.size();
        this->n = (int)board[0].size();
        this->visited = vector<vector<bool>>(m, vector<bool>(n, false));
        TrieNode* root = buildTrie(words);
        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                dfs(row, col, root);
            }
        }
        return res;
    }

    void dfs(int row, int col, TrieNode* node) {
        if (node->children[board[row][col] - 'a'] == nullptr)  return;

        node = node->children[board[row][col] - 'a'];
        if (node->word.size() > 0) {
            res.emplace_back(node->word);
            node->word = "";
        }

        visited[row][col] = true;
        // 这里如果使用 vector 会超时
        for (auto& dir : dirs) {
            int nextRow = row + dir[0];
            int nextCol = col + dir[1];
            if (nextRow >= 0 && nextRow < m && nextCol >= 0 && nextCol < n
                    && !visited[nextRow][nextCol]) {
                dfs(nextRow, nextCol, node);
            }
        }
        visited[row][col] = false;
    }

    TrieNode* buildTrie(vector<string>& words) {
        TrieNode* root = new TrieNode();
        for (const string& s : words) {
            TrieNode* curr = root;
            for (char c : s) {
                int index = c - 'a';
                if (curr->children[index] == nullptr) {
                    curr->children[index] = new TrieNode();
                }
                curr = curr->children[index];
            }
            curr->word = s;
        }
        return root;
    }
};